package 动态规划.背包And分组And切割问题系列;
import org.junit.Test;

import java.util.Scanner;
import java.io.IOException;

/**
 * 
 * 从这个 整个的过程 可以  体会 一下   Acwing Acm（模式） 的 整个代码的执行过程     和  leetcode 整个 执行代码的 源码  这两个
 * 刷题网站的  的   区别 这  两个过程是  完全不同的 
 * 一个 是  把 所有的 测试 用例 都  一次性 读入 整个 过程 就一个 类
 * 而 leetcode 这个   就离谱   一些  
 * 看他 的 源码 就知道 了 对吧 要对 java 输入 输出 还是 多多 了解 了解一下 吧 
 */
/**
 * https://www.acwing.com/problem/content/3/
 * 完全背包 问题  题目 的  链接
 */
public class Acwing完全背包问题 {
	public static void main(String []args) throws IOException {
		int N,V;
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		V  =sc.nextInt();
		int weight[] = new int [N];
		int value[] = new int [N];
		for(int i = 0;i < N;i++) {
			weight[i] = sc.nextInt();
			value[i] = sc.nextInt();
		}
		System.out.println(solution(value,weight,0,V,N));
		System.out.println(solution(value,weight,N,V));
		sc.close();
	}
	static int solution(int value[],int weight[],int index,int rest,int len) {
		if(rest == 0 || index == len)
			return 0;
		int ans = 0;
		for(int  i = index ;i < len ;i++) {
			if(rest >= weight[i]) {
				ans = Math.max(ans, solution(value,weight,i,rest - weight[i],len) + value[i]);
			}
		}
		return ans;
	}
	static int solution(int value[],int weight[],int N,int V) {
		int dp[][] = new int [N + 1][V + 1];
		for(int i = N - 1;i >= 0; i--) {
			for(int j = 1; j <= V ;j++) {
				dp[i][j] = dp[i + 1][j];
				if(j >= weight[i]) {
					dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i]] + value[i]);
				}
			}
		}
		return dp[0][V];
	}




	@Test
	public void test(){
		StringBuilder sb = new StringBuilder();
		sb.append((char)98);
//		sb.toString().trim()
	}



}
